package com.cqs.leetcode.hash;

import java.util.*;

/**
 * @author lixiaowen
 * @create 2019-12-11
 */
public class SortCharactersByFrequency451 {


    public String frequencySort(String s) {
        if (s == null || s.length() <= 2) return s;
        Map<Character, Integer> freq = new HashMap<>(512);
        char[] cs = s.toCharArray();
        for (char c : cs) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        Set<Map.Entry<Character, Integer>> entries = freq.entrySet();

        //Map.Entry<Character, Integer>[] sort = entries.stream().sorted((o1, o2) -> o2.getValue() - o1.getValue()).toArray((IntFunction<Map.Entry<Character, Integer>[]>) value -> new Map.Entry[value]);

        List<Map.Entry<Character, Integer>> sort =new ArrayList<>(entries);
        sort.sort((o1, o2) -> o2.getValue() - o1.getValue());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : sort) {
            int fre = entry.getValue();
            while (--fre >= 0) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }

    public String frequencySort2(String s) {
        if (s == null || s.length() <= 2) return s;
        Map<Character, Integer> freq = new HashMap<>(512);
        char[] cs = s.toCharArray();
        for (char c : cs) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        Set<Map.Entry<Character, Integer>> entries = freq.entrySet();
        //排序
        Map.Entry<Character, Integer>[] sort = sortDesc(entries);
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : sort) {
            int fre = entry.getValue();
            while (--fre >= 0) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }


    private Map.Entry<Character, Integer>[] sortDesc(Set<Map.Entry<Character, Integer>> entries) {
        Map.Entry<Character, Integer>[] arr = new Map.Entry[entries.size()];
        Iterator<Map.Entry<Character, Integer>> iterator = entries.iterator();
        int cnt = 0;
        while (iterator.hasNext()) {
            arr[cnt++] = iterator.next();
        }
        //排序
        quickSort(arr);
        return arr;
    }


    private void mergeSort(Map.Entry<Character, Integer>[] arr) {

    }


    private void quickSort(Map.Entry<Character, Integer>[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(Map.Entry<Character, Integer>[] arr, final int left, final int right) {
        if (arr == null || left >= right) return;
        int pivot = left;
        int l = left + 1, r = right;
        while (l <= r) {
            while (l <= r && arr[l].getValue() >= arr[pivot].getValue()) {
                ++l;
            }
            while (l <= r && arr[pivot].getValue() > arr[r].getValue()) {
                --r;
            }
            if (l < r) {
                swap(arr, l, r);
            }
        }
        swap(arr, pivot, r);
        quickSort(arr, left, r - 1);
        quickSort(arr, r + 1, right);
    }

    private void swap(Map.Entry<Character, Integer>[] arr, final int left, final int right) {
        Map.Entry<Character, Integer> tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }


    public static void main(String[] args) {
        SortCharactersByFrequency451 f = new SortCharactersByFrequency451();
        String leetCode = f.frequencySort("leetCode");
        System.out.println(leetCode);

    }




}
